package com.剑指offer.第五章;

/**
 * 有一门外星语言，它的字母表刚好包含所有的英文小写字母，只是字母表的顺序不同。给定一组单词和字母表顺序，请判断这些单词是否按照字母表的顺序排序
 * 输入一组单词["offer","is","coming"]
 */
public class 外星语言排序 {


    /**
     * 使用哈希表记录每个字符顺序出现的位置，然后循环比较两个字符串的字符顺序
     * 第一个字符串的长度比第二个字符串长 如果前面几个字符串都相同，那就判断i是否等于第一个字符串的长度，不等于说明不是按照字符顺序来的
     *
     * @param word
     * @param order
     * @return
     */
    public static boolean isAlienSorted(String[] word, String order) {
        int[] orderArray = new int[order.length()];
        for (int i = 0; i < orderArray.length; i++) {
            orderArray[order.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < word.length - 1; i++) {
            if (!isSort(word[i], word[i + 1], orderArray)) {
                return false;
            }
        }
        return true;
    }

    public static boolean isSort(String word1, String word2, int[] orderArray) {
        int i = 0;
        while (i < word1.length() && i < word2.length()) {
            char a = word1.charAt(i);
            char b = word2.charAt(i);
            if (orderArray[a - 'a'] > orderArray[b - 'a']) {
                return true;
            }
            if (orderArray[a - 'a'] > orderArray[b - 'a']) {
                return false;
            }
            i++;
        }
        return i == word1.length();
    }

    public static void main(String[] args) {

    }

}
